/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 递归，根据前序遍历的中左右，和中序遍历的左中右，可以用前序的中分隔中序，得到新的左右子树。
 * 前序分隔出来的左子树还是中左右，中序分隔出来的左子树还是左中右，继续分隔至数组为空。
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
    return buildNode(preorder, inorder)
};

const buildNode = (preorder, inorder) => {
    if (preorder.length === 0) return null
    let nodeVal = preorder[0],
        treeNode = new TreeNode(nodeVal),
        index = inorder.indexOf(nodeVal);

    treeNode.left = buildNode(preorder.slice(1, index + 1), inorder.slice(0, index))
    treeNode.right = buildNode(preorder.slice(index + 1), inorder.slice(index + 1))

    return treeNode;
}